package com.briup.day06;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class Homework {
    public static void main(String[] args) {
        // 程序运行，利用随机数生成生成一个长度为20的正整型数组。然后等待用户输入要查找的数字。
        // 1. 初始化一个长度为20的数组，内部数据元素使用[0,100]之间的随机数生成，同时内部元素不重复
        int[] arr = initArr(20);
        // Arrays是Java给数组提供的工具类，工具类中提供了数组所需的通用问题的解决方案
        System.out.println(Arrays.toString(arr));
        // 2. 查找数字，在查找数据之前可以对数组进行排序
//        sort(arr);
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        Scanner sc = new Scanner(System.in);
        while (true) {
            System.out.println("请输入您要查找的数据");
            int target = sc.nextInt();
            if (target == -1) {
                System.out.println("游戏结束！");
                break;
            }
//            int index = binarySearch(arr, target);
            int index = Arrays.binarySearch(arr, target);
            if (index == -1) {
                System.out.println("您要找的数据在数组中不存在，请继续输入其余数据");
            } else {
                System.out.printf("您输入的数据在数组中的第%s位%n", index + 1);
            }
        }
    }

    /**
     * 给指定数组进行排序
     *
     * @param arr 数组对象
     */
    public static void sort(int[] arr) {
        // 排序：冒泡排序，从小到大排序
        int n = arr.length;
        // 外层循环，控制排序轮次
        for (int i = 0; i < n - 1; i++) {
            // 给定一个变量，用于记录本轮排序中，是否存在元素交换的行为
            boolean swapped = false;
            // 内部循环控制每一次排序中，前后元素比较的个数
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    // 如果存在元素交换行为，那么将该变量修改为true
                    swapped = true;
                }
            }
            // 在本轮排序结束后，判断是否存在元素交换，如果没有元素交换，说明数组现在是有序的
            if (!swapped) break;
        }
    }

    /**
     * 在数组有序的情况下就可以使用二分查找算法
     *
     * @param arr    数组对象
     * @param target 目标数值
     * @return 该数组在数组中的下标，如果为-1说明在该数组中不存在该值
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return -1;
    }

    /**
     * 在指定数组中，查找指定的数据，返回该数据在数组的下标
     *
     * @param arr    数组对象
     * @param target 目标数值
     * @return 目标数值在数组中的下标
     */
    public static int search(int[] arr, int target) {
        /*
            能够控制循环结构进行跳出/过的手段有哪些？
              1、break：能够跳出当前循环，继续执行循环后面的代码
              2、continue：能够跳过本轮循环，继续执行迭代条件，判断循环条件，
              如果循环条件成立，那么继续执行下一轮循环
              3、return：真正作用是返回方法的返回值，即结束当前方法的运行，
              方法都结束运行了，那么方法内部的循环结构也会结束运行
         */
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 创建并初始化一个指定长度的整型数组，
     * 初始化通过随机数传入[0,100]的值
     *
     * @param length 指定数组的长度
     * @return 创建并初始化完毕的数组
     */
    public static int[] initArr(int length) {
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++) {
            arr[i] = random.nextInt(101);
            // 进行不重复检查，如果存在和前面重复的数据，那么重新生成
            for (int j = 0; j < i; j++) {
                if (arr[j] == arr[i]) {
                    // 如果当前元素值与前面的元素值重复，那么舍弃本次随机，重新随机
                    i--;
                    break;
                }
            }
        }
        return arr;
    }
}
